#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <string>
#include <cmath>
using namespace std;

class Solution
{
public:
	int totalNQueens(int n) 
	{
		// Start typing your C/C++ solution below
		// DO NOT write int main() function

		int sum = 0;

		if(n<=0)
			return 0;
		vector<int> curPos(n,0);
		vector<bool> placeHolders(n,false);
		queens(curPos,placeHolders,0,sum,n);
		return sum;
	}

private:
	void queens(vector<int>& pos, vector<bool>& placeHolders,size_t curIdx, int& num, int n)
	{
		for(int i=1;i<=n;i++)
		{
			bool valid = true;
			if(placeHolders[i-1])
				continue;
			for(size_t j=0;j<curIdx;j++)
			{
				if((curIdx-j)==abs(pos[j]-i))
				{
					valid = false;
					break;
				}
			}

			if(valid)
			{
				pos[curIdx] = i;
				placeHolders[i-1] = true;
				if(curIdx == (n-1))
				{
					num++;
				}
				else
				{
					queens(pos,placeHolders,curIdx+1,num,n);

				}

				placeHolders[i-1] = false;
			}
		}
	}



};

#endif
